package nachos.vm;

import nachos.machine.*;
import nachos.threads.*;
import nachos.userprog.*;
import nachos.vm.*;

import java.util.Formatter;

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * Data structure used to keep track of pages stored in the swap file.
 * The swap file is simply an array of pages. We keep a table in
 * memory where the ith entry in the table corresponds to the ith page
 * in the file. Each entry in the table has the page number in the
 * swap file (spn for swap page number), the pid the page belongs to,
 * the vpn (virtual page number) of the page, and valid and readOnly
 * bits. If valid is set to false, that means the page can be
 * overwritten and used for another page. We store the readOnly flag
 * so that when we put the page back into physical memory we can
 * restore the readOnly flag.
 */
public class Swap {

    private static final int pageSize = Processor.pageSize;

    private final String filename;

    /**
     * The file we use to store the pages.
     */
    final OpenFile file;

    /**
     * Table used to keep track of the pages currently in the file.
     */
    List<Entry> table = new ArrayList<Entry>();

    /**
     * Maps a (pid, vpn) pair to its index in the table.
     */
    private final Map<List<Integer>, Integer> index =
	new HashMap<List<Integer>, Integer>();

    /**
     * Make a new Swap with n pages, backed by the file with the given
     * name.
     */
    public Swap(int n, String filename) {
	this.filename = filename;
	file = VMKernel.fileSystem.open(filename, true);
    }

    /**
     * An entry in our table.
     */
    public static class Entry {
	final int spn;
	int pid;
	int vpn;
	boolean valid;
	boolean readOnly;

	private Entry(int spn) {
	    this.spn = spn;
	}

	void invalidate() {
	    valid = false;
	    pid = -1;
	}
    }

    /**
     * Write a page of physical memory to the swap file and put a
     * record of it in our table.
     */
    public void write(int pid, int vpn, int ppn, boolean readOnly) {

	int spn = table.size();;

	// First try to see if we've already allocated a slot for this
	// page. If so, just save it there.
	Integer idx = index.get(key(pid, vpn));
	
	if (idx != null &&
	    table.get(idx).pid == pid &&
	    table.get(idx).vpn == vpn)
	    spn = idx;

	if (spn < table.size()) {
	    Lib.debug(VMProcess.dbgVM, "Already have it at slot " + spn);
	}

	// If not, look for an invalid page.
	if (spn == table.size()) {
	    for (spn = 0; spn < table.size(); spn++) {
		if (!table.get(spn).valid)
		    break;
	    }

	    if (spn == table.size()) {
		Entry e = new Entry(table.size());
		e.pid = -1;
		e.vpn = -1;
		e.valid = false;
		e.readOnly = false;
		table.add(e);
	    }
	}

	Lib.debug(VMProcess.dbgVM, "putting it in slot " + spn);

	// Record this page in our table
	Entry e = table.get(spn);
	e.pid = pid;
	e.vpn = vpn;
	e.valid = true;
	e.readOnly = readOnly;

	// Add it to the index
	index.put(key(pid, vpn), spn);

	// Write the page to the swap file
	int pos = spn * pageSize;
	int off = ppn * pageSize;
	byte[] mem = Machine.processor().getMemory();
	file.write(pos, mem, off, pageSize);
    }

    /**
     * Read a page from swap back into physical memory.
     */
    public Entry read(int pid, int vpn, int ppn) {

	int spn = table.size();

	Integer idx = index.get(key(pid, vpn));
	if (idx != null &&
	    table.get(idx).pid == pid &&
	    table.get(idx).vpn == vpn &&
	    table.get(idx).valid)
	    spn = idx;

	if (spn == table.size())
	    {
		return null; // page hasn't been loaded from executable or unallocated stack
		//throw new RuntimeException("Don't have entry for (" + 
		//			   pid + ", " + vpn + ") in swap");
	    }

	int pos = spn * pageSize;
	int off = ppn * pageSize;
	byte[] mem = Machine.processor().getMemory();
	int amount = file.read(pos, mem, off, pageSize);


	if (amount != pageSize) {
	    throw new RuntimeException("Read wrong amount from swap file");
	}

	return table.get(spn);
    }

    public String toString() {
	Formatter f = new Formatter()
	    .format("%n")
	    .format("%6s %6s %6s %5s %5s%n",
		    "PID", "VPN", "SPN", "Valid", "R.O.");

	for (Entry e : table) {
	    f.format("%6d %6d %6d %5b %5b%n",
		     e.pid, e.vpn, e.spn, e.valid, e.readOnly);
	}
	return f.toString();
    }
    
    public void close() {
	file.close();
	VMKernel.fileSystem.remove(filename);
    }

    private List<Integer> key(int pid, int vpn) {
	return Arrays.asList(pid, vpn);
    }

    public void invalidateProcess(int pid) {
	for (Entry e : table) {
	    if (e.pid == pid) {
		e.invalidate();
	    }
	}
    }
}